package com.lisp.algorithm.sort;

import com.lisp.algorithm.util.SortUtil;

/**
 * 1. 对数组x[]和y[], 如果x[i]<=y[i]成立，即：x[0]<=y[0], x[1]<=y[1],....
 *    对x[]和y[]分别独立排序后，x[i]<=y[i]依然成立
 *    证明：排序后，y[i]>=排在y[i]前面的y[0]~y[i-1]，加上y[i]本身，y[i]>=i+1个y
 *         又每个y都>=某个x，所以y[i]>=i+1个y，自然>=i+1个x
 *         x[]排序后，>=i+1个x，自然>=前i+1个x，自然>=第i+1个x，即x[i]
 *         综上: y[i] >= x[i]
 * 
 * 2. k排序好的数组，进行h排序后，依然是k排序的
 *    比如：对5排序好的数组，进行3排序操作
 *    3排序前，子数组1中的元素    a[0], a[3], a[6], a[9]...
 *      对应<=子数组2中的元素   a[5], a[8], a[11], a[14]...
 *    3排序，就是对子数组1和2，分别排序
 *    根据1中的引理，分别排序后，子数组1中的元素依然对应<=子数组2中的元素
 *    同理可证: {a[1], a[4]...} 对应<= {a[6], a[9]...}
 *            {a[2], a[5]...} 对应<= {a[7], a[10]...}
 *    合起来就证明了3排序后，依然是5排序的
 * @author liushuai21
 *
 */
public class ShellSort {

    public static void main(String[] args) {
        SortUtil.test(ShellSort::shellSort);
    }
    
    
    private static void shellSort(int a[]) {
        for(int gap=a.length/2; gap>=1; gap=gap/2) {
            for(int i=gap; i<a.length; i++) {
                int insertIndex = i;
                int insertVal = a[insertIndex];
                while(insertIndex >= gap && insertVal < a[insertIndex-gap]) {
                    a[insertIndex] = a[insertIndex - gap];
                    insertIndex = insertIndex - gap;
                }
                a[insertIndex] = insertVal;
            }
        }
    }
    
}
